package me.algo.rec;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/5/22
 */
public class R4 {

    public static void main(String[] args) {
        List<String> strings = letterCombinations("23");
        System.out.println(strings);
    }

    /**
     * 17. 电话号码的字母组合
     * @param digits
     * @return
     */
    public static List<String> letterCombinations(String digits) {
        if (Objects.isNull(digits) || digits.isEmpty()) {
            return new ArrayList<>();
        }
        int len = digits.length();
        List<String> rtn = new ArrayList<>();
        LinkedList<StringBuilder> que = new LinkedList<>();
        char[] cha = digits.toCharArray();
        int idx = 0;
        do {
            char c = cha[idx];
            List<Character> chList = MP.get(c);

            if (idx == 0) {
                for (Character ch : chList) {
                    StringBuilder nb = new StringBuilder();
                    nb.append(ch);
                    if (nb.length() == len) {
                        rtn.add(nb.toString());
                    }else {
                        que.addLast(nb);
                    }
                }
            } else {
                int size = que.size();
                while (size > 0) {
                    size--;
                    StringBuilder preList = que.removeFirst();
                    for (Character ch : chList) {
                        String preStr = preList.toString();
                        StringBuilder nb = new StringBuilder(preStr);
                        nb.append(ch);
                        if (nb.length() == len) {
                            rtn.add(nb.toString());
                        }else {
                            que.addLast(nb);
                        }
                    }
                }
            }
            idx++;
        } while (!que.isEmpty() && idx < len);
        return rtn;
    }

    final static Map<Character, List<Character>> MP = HashMap.newHashMap(8);
    static {
        MP.put('2', List.of('a', 'b', 'c'));
        MP.put('3', List.of('d', 'e', 'f'));
        MP.put('4', List.of('g', 'h', 'i'));
        MP.put('5', List.of('j', 'k', 'l'));
        MP.put('6', List.of('m', 'n', 'o'));
        MP.put('7', List.of('p', 'q', 'r', 's'));
        MP.put('8', List.of('t', 'u', 'v'));
        MP.put('9', List.of('w', 'x', 'y', 'z'));
    }
}
